package org.example.leetcode.interview.linkedlist;

import org.example.util.IO;
import org.example.util.ListNode;

public class LC0019 {
    /**
     * 快指针先移动n次, 随后慢指针快指针同时移动至快指针为null
     * 此时慢指针指向的节点就是要删除的节点, 使用prev指针删除
     * @param head
     * @param n
     * @return
     */
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;

        ListNode slow = dummy;
        ListNode fast = dummy;
        while (n-- > 0) {
            fast = fast.next;
        }

        ListNode prev = null;
        while (fast != null) {
            prev = slow;
            fast = fast.next;
            slow = slow.next;
        }
        prev.next = slow.next;

        return dummy.next;
    }

    public static void main(String[] args) {
        LC0019 solu = new LC0019();
        solu.removeNthFromEnd(IO.intLinkedList("[1,2,3,4,5]"), 2);
        solu.removeNthFromEnd(IO.intLinkedList("[1,]"), 1);
        solu.removeNthFromEnd(IO.intLinkedList("[1, 2]"), 1);
    }
}
